class Solution {//leetcode980——不同路径III
private:
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    pair<int,int> init_grid(vector<vector<int>>& grid){
        int cnt=0;
        pair<int,int> start(0,0);
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==1)
                {
                    cnt++;
                    start=make_pair(i,j);
                }
                else if(grid[i][j]==-1){
                    used[i][j]=true;
                }
                else if(grid[i][j]==0||grid[i][j]==2)
                    cnt++;
            }
        }
        step=cnt;
        return start;
    }
    void _dfs(vector<vector<int>>&grid,int rows,int cols,int path){
        used[rows][cols]=true;
        if(grid[rows][cols]==2){
            used[rows][cols]=false;
            if(path!=step) return;
            ret++;
            return;
        }
        for(int i=0;i<4;i++){
            int x=cols+dx[i],y=rows+dy[i];
            if(x>=0&&x<n&&y>=0&&y<m&&used[y][x]==false){
                _dfs(grid,y,x,path+1);
            }
        }
        used[rows][cols]=false;
    }
public:
    int uniquePathsIII(vector<vector<int>>& grid) {
        m=grid.size();
        n=grid[0].size();
        used.resize(m,vector<bool>(n,false));
        pair<int,int> start =init_grid(grid);//start.first=rows,start.second=cols
        _dfs(grid,start.first,start.second,1);
        return ret;
    }
private:
    int m;
    int n;
    vector<vector<bool>> used;
    int step;
    int ret=0;
};